/**
 *@auther:Chen
 *@createTime: 2020/4/23 21:57
 *@description:
 * 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
 *
 * 示例1:
 *
 * 输入: n = 5
 * 输出：2
 * 解释: 有两种方式可以凑成总金额:
 * 5=5
 * 5=1+1+1+1+1
 * 示例2:
 *
 * 输入: n = 10
 * 输出：4
 * 解释: 有四种方式可以凑成总金额:
 * 10=10
 * 10=5+5
 * 10=5+1+1+1+1+1
 * 10=1+1+1+1+1+1+1+1+1+1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/coin-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 **/
fun main() {
	println(waysToChange(10))
}

private fun waysToChange(n: Int): Int {
	val money = intArrayOf(1, 10, 5, 25)
	val mod = 1000000007
	val ans = IntArray(n + 1)
	ans[0] = 1
	money.forEach { m ->
		for (i in m..n) {
			ans[i] = (ans[i] + ans[i - m]) % mod
		}
	}
	return ans[n]
}